\documentclass[10pt,a4paper,titlepage]{article}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{color}
\usepackage{float}
\usepackage{rotating}
\usepackage{array}

\title{Advanced Algorithms 2012\\Assignment 1: Max flow/linear programming}

\author{Benjamin Johannes Ertl \{gfq406@alumni.ku.dk\}\\Justinas Murzinas \{snp982@alumni.ku.dk\} }

%\institute{Department of Computer Science\\
%University of Copenhagen

%\pagestyle{plain}

\begin{document}

\maketitle

\section*{Question 1}

The company could efficiently determine the largest transfer rate to the server, by using the Edmonds-Karp algorithm to determine the maximum flow in the network. The algorithm runs in time $\mathcal{O}(VE^2)$, where $V$ denotes the number of vertices/nodes in the flow network and $E$ the number of edges. To use the algorithm, the computer network must be converted into a flow network.

Therefore, we add an additional single source node, the supersource, that is connected to all source nodes (workstations) with directed edges with infinite capacity. This is necessary, to convert the problem with multiple sources to a ordinary maximum flow problem with a single source for applying the algorithm. The infinite capacity ensures, that we can put as much flow out of the supersource to the multiple sources as possible.

All workstations and relay stations become nodes in the network, the server becomes the sink node.

Each connection in the network, except the connections going to the server and coming from the supersource, corresponds to an bidirectional edge in the flow network, because all workstations and relay stations can receive and transmit data, that means that data can flow in both directions on each connection.

We transform each bidirectional/antiparallel edge to a non-antiparallel edge in the following way, see Figure \ref{fig:q1}.

\begin{figure}[H]
\begin{center}
\includegraphics
[width=0.5\linewidth]{edge.png}
\end{center}
\caption{Antiparallel to non-antiparallel transformation}
\label{fig:q1}
\end{figure}

We split each edge into two edges with opposite directions to avoid bidirectional edges. To avoid the so originated antiparallel edges, we split one edge and add an additional vertex in-between. The initial capacity remains the same on all edges.

The transformation is only done in the network model and does not affect the original physical network. It is necessary, to be conform with the flow network definition and to apply the algorithm.

\section*{Question 2}
The maximum flow problem can be expressed as a linear program as described in \cite{1}[p. 860f.] and can be written as following.

\[
\text{MAX    } \sum_{v \in V} f_{sv} - \sum_{v \in V} f_{vs}
\]
\begin{eqnarray*}
\text{S.T.    } f_{uv} \leq c(u, v),~ u, v \in V \\
\sum_{v \in V} f_{vu} = \sum_{v \in V} f_{uv},~ u \in V - \{s,t\} \\
f_{uv} \geq 0,~ u, v \in V \\
\end{eqnarray*}

\section*{Question 3}
A small example graph could look like following.

\begin{figure}[H]
\begin{center}
\includegraphics
[width=0.5\linewidth]{example.png}
\end{center}
\caption{Example graph}
\label{fig:q3}
\end{figure}

The linear program to this example can be written as following.

\[
\text{MAX    } f_{s1} + f_{s2}
\]
\begin{eqnarray*}
\text{S.T.    } f_{s1} = f_{1t} \\
               f_{s2} = f_{2t} \\
               f_{s1} \leq 3 \\
               f_{s2} \leq 3 \\
               f_{1t} \leq 2 \\
               f_{2t} \leq 2 \\
               f_{vu} \geq 0, ~ (v,u) \in E
\end{eqnarray*}

The optimal solution for the example would be $f_{s1} = 2, f_{s2} = 2$ with the maximum flow of $4$.

\section*{Question 4}
The cheapest critical connection could efficiently be determined by computing the minimum cut of the computer network converted to a flow network and increasing the capacity of the connection with the minimal transfer rate in the edges that connect the two sets of vertices. The connection with the minimal transfer rate among the minimum cut connections between the two subsets of vertices has the minimal cost by increasing. If the maximum flow has not changed after increasing that connection we repeat the procedure and remembering the costs of the edges we did not increase. If increasing an other edge's transfer rate is then in any other additional step higher then it would be increasing only one connection with lower costs, we revert the process and take increase this one connection and continue.

\section*{Question 5}
The dual of the linear program example in Question 3 can be written as following.

\[
\text{MIN    } 3y_5 + 3y_6 + 2y_7 + 2y_8
\]
\begin{eqnarray*}
\text{S.T.    } y_1 - y_3 + y_5 \geq 1 \\
                y_2 - y_4 + y_6 \geq 1 \\
                -y_1 + y_3 + y_7 \geq 0 \\
                -y_2 + y_4 + y_8 \geq 0 \\
                y_i \geq 0, i = 1..8
\end{eqnarray*}

\section*{Question 6}
Critical connections can be determined by using the method described in the bottom of \cite[p.~881]{1} and by using equation (29.91) in the next page. The result of last slack form of the primal in our example was:
\[z = 4 - x_5 - x_7 - x_{11} - x_{12}\]
Since $n=4$, we only care about last $8$ coefficients, so we take the negatives of these coefficients: \[\bar{y} = (1,0,1,0,0,0,1,1)\]
The non-zero values here indicate the critical connections.

We then use these values to calculate the optimal solution to the dual, which is also the max flow: $3*0 + 3*0 + 2*1 + 2*1 = 4$.

\section*{Question 7}
The lowest possible price the company has to pay can be solved as a minimum-cost-flow problem, described in \cite[p.~861]{1}:
\begin{eqnarray*}
& \text{minimize} & \sum_{(u,v) \in E} a(u,v)f_{uv} \\
& \text{subject to} & f_{uv} \leq c(u, v) \text{,  for each } u, v \in V	\\
& &\sum_{v \in V} f_{vu} - \sum_{v \in V} f_{uv} = 0 \text{,  for each } u \in V - \{s,t\}	\\
& &\sum_{v \in V} f_{sv} - \sum_{v \in V} f_{vs} = d \\
& &f_{uv} \geq 0 \text{,  for each } u, v \in V
\end{eqnarray*}

Where $d$ is the previously determined maximum transfer rate, and $a(u,v)$ is the cost of an edge. Since the leasing price is 1 øre for each byte transferred in and out of the other company's network, we only need to assign the value of 1 to the edges going in the nodes of those companies. So:
\[
  a(u,v) = \left\{ 
  \begin{array}{l l}
    1 & \quad \text{for each $v \in V_o$ (other company)}\\
    0 & \quad \text{otherwise}\\
  \end{array} \right.
\]

\section*{Question 8}
The largest bit rate for the given network was computed as $95$, the lowest leasing-price as $60$. For the lowest price we assumed, that each flow in and out of the cost-network increases the total cost. The results were obtained by formulating the linear programs from Question 2 and 7 in Python (2.7.1) using the pulp-or linear program library (1.4.6) for Windows 7. We created a two-dimensional list of the capacities, where each dimension represents a node, and used an other similar list for the costs. The linear programs with all constraints were then model and solved with pulp-or.

\begin{thebibliography}{9}
\bibitem[ITA]{1}
Thomas H. Cormen,
Introduction To Algorithms,
2009.
\end{thebibliography}

\end{document}
